import com.kiwi.nixu.common.LNode;

/**
 * K链表翻转是指把每K个相邻的结点看成一组进行翻转，如果剩余结点不足K个，则保持不变。
 * 假设给定链表1→2→3→4→5→6→7和一个数K，
 * 如果K的值为2，那么翻转后的链表为2→1→4→3→6→5→7。
 * 如果K的值为3，那么翻转后的链表为3→2→1→6→5→4→7
 */
public class H如何把链表以K个节点为一组进行翻转 {

    /**
     * 主要思路为：
     * 首先把前K个结点看成一个子链表，采用前面介绍的方法进行翻转，
     * 把翻转后的子链表链接到头结点后面，然后把接下来的K个结点看成另外一个单独的链表进行翻转，
     * 把翻转后的子链表链接到上一个已经完成翻转子链表的后面。具体实现方法如下图所示
     */

    private static LNode reverse(LNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        LNode pre = head;//前驱节点
        LNode cur = head.next;//当前节点
        LNode next = cur.next;//后继节点
        pre.next = null;
        while (cur != null) {
            next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = cur.next;
            cur = next;
        }
        return pre;
    }

    //对链表K翻转
    public static void reverseK(LNode head, int k) {
        if (head == null || head.next == null || k < 2) {
            return;
        }
        int i = 1;
        LNode pre = head;
        LNode begin = head.next;
        LNode end = null;
        LNode pNext = null;
        while (begin != null) {
            end = begin;
            for (; i < k; i++) {
                if (end.next != null) {
                    end = end.next;
                } else {
                    return;
                }
            }
            pNext = end.next;
            end.next = null;
            pre.next = reverse(begin);
            begin.next = pNext;
            pre = begin;
            begin = pNext;
            i = 1;
        }
    }

    public static void main(String[] args) {

        int i = 1;
        LNode head = new LNode();
        head.next = null;
        LNode tmp;
        LNode cur = head;
        for (; i < 8; i++) {
            tmp = new LNode();
            tmp.data = i;
            tmp.next = null;
            cur.next = tmp;
            cur = tmp;
        }
        System.out.println("顺序输出");
        for (cur = head.next; cur != null; cur = cur.next) {
            System.out.print(cur.data + "");
        }
        reverseK(head, 3);
        System.out.println("\n逆序输出");
        for (cur = head.next; cur != null; cur = cur.next) {
            System.out.print(cur.data + "");
        }

        for (cur = head.next; cur != null; ) {
            cur = cur.next;
        }
    }
}
